#include <stdio.h>
#include <stdlib.h>

int fun(int x, int y, int n)
{
    int num = y * n / (x + y);
    int mod = y * n % (x + y);

    if (mod == 0) {
        return x + y;
    } else {
        return (num + 1) * (x + y) - (y * n);
    }
}

int main (int argc, char const* argv[])
{
    int n, m, up, down, x, ans;

    scanf("%d %d", &n, &m);

    ans = 100000000;
    while (m--) {
        scanf("%d %d", &up, &down);
        x = fun(up, down, n);
        if (x < ans) {
            ans = x;
        }
    }

    printf("%d\n", ans);

    return 0;
}
